import java.util.Scanner;

public class Main {
    /**
     * ACM环境下运行的01背包问题
     * 时间复杂度O（n*n）
     * 空间复杂度O（n*n）*/
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        //输入
        int n = in.nextInt();//物品个数
        int V = in.nextInt();//背包体积
        //item从1 1 开始输入，故多创建一行多创建一列 1代表物品体积，2代表物品价值
        int[][] item = new int[n+1][3];
        for(int k = 1; k <= n; k++) {
            item[k][1] = in.nextInt();
            item[k][2] = in.nextInt();
        }

        //1 创建dp表 - 虚拟位置法，多创建一行一列
        int[][] dp = new int[n+1][V+1];
        int[][] dpp = new int[n+1][V+1];
        //2 初始化 - 仅对dpp第一行1下标之后的元素进行初始化
        for(int k = 1; k <= V; k++)
            dpp[0][k] = -1;
        //3 填表
        int[] ret = new int[2];//0 代表第一问答案 1代表第二问答案
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= V; j++) {
                int tmp = j-item[i][1];
                //(1)
                dp[i][j] = dp[i-1][j];
                if(tmp>=0) dp[i][j] = Math.max(item[i][2]+dp[i-1][tmp],dp[i][j]);
                ret[0] = Math.max(dp[i][j],ret[0]);
                //(2)
                dpp[i][j] = dpp[i-1][j];
                if(tmp>=0 && dpp[i-1][tmp]!=-1) dpp[i][j] = Math.max(item[i][2]+dpp[i-1][tmp],dpp[i][j]);
                if(j==V) ret[1] = Math.max(dpp[i][j],ret[1]);
            }
        }
        //4 返回值
        System.out.println(ret[0]);
        System.out.println(ret[1]);
    }

    /**
     * 分割等和子集
     * 时间复杂度O（n*n）
     * 空间复杂度O（n*n）*/
    public boolean canPartition(int[] nums) {
        /**
         由题意可得，我们需要对一个数组进行操作，判断它是否可以分成两个元素和相等的集合
         即:
         假设数组总和为sum，那么则需要我们在数组中挑选一些元素，使其组成的集合元素和为sum/2
         若是能组成，则返回true，否则返回false
         不过在解题之前，我们需要明白，若是num为单数，那么其一定不能分成两个元素和相等的集合，因为每个元素都是int类型，不存在小数
         */
        int n = nums.length;
        int sum = 0;
        for(int i = 0; i < n; i++)
            sum+=nums[i];
        //特判
        if(sum%2!=0 || n==1) return false;
        //此时我们只需要判断数组中的元素是否能组成sum/2即可
        /**
         状态表示：
         dp[i][j]表示前i个元素所有选法中，能否凑成j这个数
         状态转移方程：
         我们还是以最后一个元素进行划分问题
         我们不选i下标元素：dp[i][j] = dp[i-1][j];
         我们选择i下标元素：j>=nums[i] ==> dp[i][j] = dp[i-1][j-nums[i]];
         填表顺序：
         从上到下
         初始化：
         与引入空串的思想一致，我们不能单独去看某个虚拟位置的值，而是需要将其定义后再判断
         使用虚拟位置法进行初始化
         虚拟位置赋值 - 多初始化一行一列：
         dp[0][0]表示，我们在挑选前0个下标时，能否凑成0，由于0下标没有元素，故其值为0，dp[0][0]=true
         第一行从1下标开始表示的是，当我们在挑选前0个下标时，能否凑成1/2/3/4...由于前0个元素值为0，故无法凑成，均为false
         第一列从1下标开始表示的时，当我们在挑选前1/2/3/4..个下标时，能否凑成0，我们只需要不选择元素即可凑成，故均为true
         */
        int target = sum/2;
        //1 创建dp表 - 使用虚拟位置法进行初始化 多创建一行一列
        boolean[][] dp = new boolean[n+1][target+1];
        //2 初始化
        for(int k = 0; k <= n; k++)
            dp[k][0] = true;
        //3 填表 - 由于是数组，故当我们使用虚拟位置法时需要注意下标的映射关系
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= target; j++)
                dp[i][j] = dp[i-1][j] || j>=nums[i-1]&&dp[i-1][j-nums[i-1]];

        //4 返回值
        return dp[n][target];
    }

/*      使用滚动数组进行优化
        分割等和子集
        时间复杂度O（n*n）
        空间复杂度O（n）
        public boolean canPartition(int[] nums) {
        //求数组元素总和
        int sum = 0;
        int n = nums.length;
        for(int k = 0; k < n; k++)
            sum+=nums[k];
        //对sum为单数 或 n等一 的情况进行特判
        if(sum%2!=0 || n==1) return false;
        //设定目标值
        int target = sum/2;

        //1 创建dp表
        boolean[] dp = new boolean[target+1];
        //2 初始化
        dp[0] = true;
        //3 填表
        for(int i = 1; i <= n; i++)
            //为了保证在遍历时，我们能够使用上一行的状态，故我们将内层循环调整为从后向前遍历
            for(int j = target; j >= 1; j--)
                dp[j] = dp[j] || j>=nums[i-1]&&dp[j-nums[i-1]];
        return dp[target];
    }*/

    public int findTargetSumWays(int[] nums, int target) {
        /**
         在做本题时，我们已提前知道本题可以使用01背包的思想去解决 故我们尝试将问题进行转换
         题目转换：
         由本题可得，我们需要向数组中每个元素前添加一个“+”或者“-”
         那么我们就可将这个数组分为两部分：
         a 由该数组中所有添加“+”号的元素组成（正数），并定义a中所有元素总和为 aAll
         b 由该数组中所有添加“-”号的元素组成 （负数），并定义b中所有元素总和为 bAll
         那么target = aAll+bAll
         也有aAll-bAll = sum(数组元素总和-为操作前的)
         联立1式和2式可得：
         2*aAll = sum+target
         aAll = (sum+target)/2
         由这个式子我们可以求得aAll的值，在这个数组中，所有 元素和为aAll的集合 都可以使得该表达式为target
         故我们只需要求得 在该数组中选出一部分元素，使其元素和恰好为aAll 的选择方案数量即可
         状态表示：
         dp[i][j]表示在前i个元素中 挑选一些元素使其元素和值恰好为j 的挑选方案数量
         状态转移方程：
         以最后一个元素的状态进行划分问题：
         1，我们不选择i下标元素：dp[i][j] = dp[i-1][j]
         2，我们选择i下标元素：首先要保证j>=nums[i],在满足此条件的情况下，dp[i][j] = dp[i-1][j-nums[i]]
         由于是方案总和 故dp[i][j]等于这两种方法的总和
         初始化：
         引入空串的思想+虚拟位置法
         dp[0][0]表示0个元素，挑出一些元素，使其元素和为0的操作方案，共一种，故dp[0][0]=1
         第一行从1下标开始，表示的是0个元素，挑出一些元素，使其元素和为1/2/3/4..的操作方案，均为0
         第一列从1下标开始，表示的是前1/2/3/4...个元素，挑出一些元素，使其元素和为0的操作方案，都不选即是为0，共一种
         需要注意下标映射关系

         填表顺序：
         在我们填写第n行时，其依赖于第n-1行的数据
         故填表顺序为从上到下  */

        //求数组总和
        int sum = 0;
        for(int x: nums) {
            sum+=x;
        }
        int n = nums.length;
        //设定目标值
        int objective = (sum+target)/2;
        //处理边界情况 target可能是负数
        if(objective<0 || (sum+target)%2==1) return 0;
        //1 创建dp表 - 使用虚拟位置法，多创建一行一列
        int[][] dp = new int[n+1][objective+1];
        //2 初始化
        for(int k = 0; k <= n; k++)
            dp[k][0] = 1;
        //3 填表
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= objective; j++)
                dp[i][j] = j>=nums[i-1] ? dp[i-1][j-nums[i-1]]+dp[i-1][j] : dp[i-1][j];
        //4 返回值
        return dp[n][objective];
    }

    /**
     * 正确的解题-上文中的解题 在初始化时忽略了0的存在*/
    public int findTargetSumWaysOther(int[] nums, int target) {
        /**
         在做本题时，我们已提前知道本题可以使用01背包的思想去解决 故我们尝试将问题进行转换
         题目转换：
         由本题可得，我们需要向数组中每个元素前添加一个“+”或者“-”
         那么我们就可将这个数组分为两部分：
         a 由该数组中所有添加“+”号的元素组成（正数），并定义a中所有元素总和为 aAll
         b 由该数组中所有添加“-”号的元素组成 （负数），并定义b中所有元素总和为 bAll
         那么target = aAll+bAll
         也有aAll-bAll = sum(数组元素总和-为操作前的)
         联立1式和2式可得：
         2*aAll = sum+target
         aAll = (sum+target)/2
         由这个式子我们可以求得aAll的值，在这个数组中，所有 元素和为aAll的集合 都可以使得该表达式为target
         故我们只需要求得 在该数组中选出一部分元素，使其元素和恰好为aAll 的选择方案数量即可
         状态表示：
         dp[i][j]表示在前i个元素中 挑选一些元素使其元素和值恰好为j 的挑选方案数量
         状态转移方程：
         以最后一个元素的状态进行划分问题：
         1，我们不选择i下标元素：dp[i][j] = dp[i-1][j]
         2，我们选择i下标元素：首先要保证j>=nums[i],在满足此条件的情况下，dp[i][j] = dp[i-1][j-nums[i]]
         由于是方案总和 故dp[i][j]等于这两种方法的总和
         初始化：
         引入空串的思想+虚拟位置法
         dp[0][0]表示0个元素，挑出一些元素，使其元素和为0的操作方案，共一种，故dp[0][0]=1
         第一行从1下标开始，表示的是0个元素，挑出一些元素，使其元素和为1/2/3/4..的操作方案，均为0
         --第一列需要注意，nums中的元素是有可能为0的，故此时我们还需要计算才可以得到正确的答案
         第一列从1下标开始，表示的是前1/2/3/4...个元素，挑出一些元素，使其元素和为0的操作方案，都不选即是为0，共一种
         需要注意下标映射关系

         填表顺序：
         在我们填写第n行时，其依赖于第n-1行的数据
         故填表顺序为从上到下  */

        //求数组总和
        int sum = 0;
        for(int x: nums) {
            sum+=x;
        }
        int n = nums.length;
        //设定目标值
        int objective = (sum+target)/2;
        //处理边界情况 target可能是负数
        if(objective<0 || (sum+target)%2==1) return 0;
        //1 创建dp表 - 使用虚拟位置法，多创建一行一列
        int[][] dp = new int[n+1][objective+1];
        //2 初始化
        dp[0][0] = 1;
        //3 填表
        for(int i = 1; i <= n; i++)
            for(int j = 0; j <= objective; j++)
                dp[i][j] = j>=nums[i-1] ? dp[i-1][j-nums[i-1]]+dp[i-1][j] : dp[i-1][j];
        //4 返回值
        return dp[n][objective];
    }


}